home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2004 April / Gamestar_61_2004-04_dvdb.iso / DVDStar / Editace / hltp.exe / {app} / Applications / QuArK / quarkpy / b2utils.py < prev    next >
Encoding:
Python Source  |  2004-01-05  |  15.9 KB  |  585 lines
  1. """   QuArK  -  Quake Army Knife
  2.  
  3. Various quadratic bezier utilities.
  4. """
  5.  
  6. #
  7. # by tiglari@hexenworld.com, May 2000
  8. #
  9. #THIS FILE IS PROTECTED BY THE GNU GENERAL PUBLIC LICENCE
  10. # FOUND IN FILE "COPYING.TXT"
  11. #
  12.  
  13. #$Header: /cvsroot/quark/runtime/quarkpy/b2utils.py,v 1.18 2002/12/29 04:18:33 tiglari Exp $
  14.  
  15.  
  16. import math
  17. import quarkx
  18. from maputils import *
  19.  
  20. #
  21. # Here should go things of general utility for managing
  22. #  quadratic bezier patches
  23. # 
  24.  
  25.  
  26.  
  27. within45 = math.cos(deg2rad*45)
  28.  
  29. def iseven(num):
  30.   return not divmod(num,2)[1]
  31.  
  32. def linearcomb(C, P):
  33.  "linear combination"
  34.  return reduce(lambda x,y:x+y, map(lambda p,c:c*p,C,P))
  35.  
  36. def extend_distance_by(v1, v2, ext):
  37.   "v1 plus distance from v1 to v2 times ext"
  38.   return v1 + ext*(v2-v1)
  39.  
  40.  
  41. #
  42. # Some useful things for Quadratic Beziers
  43. #
  44.  
  45. def rowofcp(cp, i):
  46.     return cp[i]
  47.     
  48. def colofcp(cp, j):
  49.     return map(lambda row,j=j:row[j], cp)
  50.     
  51. def lengthof(line, divs):
  52.     if divs<0:
  53.       return
  54.     sum=0
  55.     for i in range((len(line)-1)/2):
  56.       k = 2*i
  57.       sum=sum+lengthofseg(line[k], line[k+1], line[k+2], divs)
  58.     return sum
  59.     
  60. #
  61. # If this were going to get out into generally applying non-UI
  62. #   routines, it might be worth shifting it into delphi.
  63. #
  64. def lengthofseg(p0, p1, p2, divs):
  65.     "approximates length of b2 line segment, splitting into 2^divs segments"
  66.     if divs == 0:
  67.        return abs(p2-p0)
  68.     else:
  69.        m = b2midpoint(p0, p1, p2)
  70.        q1 = b2qtpoint(p0, p1, p2)
  71.        q3 = b2qt3point(p0, p2, p2)
  72.        m0 = b2midcp(p0, q1, m)
  73.        m1 = b2midcp(m, q3, p2)
  74.        return lengthofseg(p0, m0, m, divs-1)+lengthofseg(m, m1, p2, divs-1)
  75.        
  76. def b2midpoint(p0, p1, p2):
  77.   "midpoint of the b2 line for the three points"
  78.   return 0.25*p0 + 0.5*p1 + 0.25*p2
  79.   
  80. def b2qtpoint(p0, p1, p2):
  81.   "1 quarter point of the b2 line for the three points"
  82.   return (9/16.0)*p0+(3/8.0)*p1+(1/16.0)*p2
  83.  
  84. def b2qt3point(p0, p1, p2):
  85.   "3 quarter point of the b2 line for the three points"
  86.   return (1/16.0)*p0+(3/8.0)*p1+(9/16.0)*p2
  87.  
  88. def b2midcp(p0, m, p2):
  89.   "cp to get b2 line from p0 to p2 passing thru m"
  90.   return 2.0*m-0.5*(p0+p2)
  91.  
  92.  
  93.  
  94. def interpolateGrid(p0, p1, p2, p3, h=3, w=3):
  95.     "makes a bezier from the four points"
  96.     "p0, ..., p1 top row, p2,..., p3 bottom"
  97.     cp = []
  98.     h, w = float(h), float(w)
  99.     H, W = h-1, w-1
  100.     upfront, upback = (p2-p0)/(h-1), (p3-p1)/(h-1)
  101.     for i in range(h):
  102.         front, back = p0+i*upfront, p1+i*upback
  103.         across = (back-front)/(w-1)
  104.         row = []
  105.         for j in range(w):
  106.             #
  107.             # non 3x3 cp's need to be 5-space
  108.             #
  109.             row.append(quarkx.vect((front+j*across).tuple+(i/H,j/W)))
  110.         cp.append(row)
  111.     return cp
  112.  
  113.  
  114. def transposeCp(cp):
  115.     "returns cp transposed"
  116.     new = map(lambda x:[],range(len(cp[0])))
  117.     for j in range(len(new)):
  118.         for row in cp:
  119.             new[j].append(row[j])
  120.     return new
  121.  
  122.  
  123. #
  124. # This seems to be needed because copy.deepcopy() non sembra functionare
  125. #
  126. def copyCp(cp):
  127.     "returns a copy of the cp array"
  128.     return map(lambda row:map(lambda v:v, row), cp)
  129.  
  130. def mapCp(f, cp):
  131.     "returns a new cp array with f applied to each member of cp"
  132.     return map(lambda row,f=f:map(f, row), cp)
  133.  
  134. def texcpFromCp(cp, cp2):
  135.     "tex coords of 2nd cp net are transferred to first"
  136.     if len(cp)!=len(cp2) or len(cp[0])!=len(cp2[0]):
  137.       quarkx.msgbox("transferTexcp dimension mismatch",2,4)
  138.       return
  139.     def maprow(row, row2):
  140.         return map(lambda v, v2:quarkx.vect(v.xyz+v2.st), row, row2)
  141.     return map(maprow, cp, cp2)
  142.  
  143.     
  144. def listCp(cp):
  145.     cp2 = []
  146.     for row in cp:
  147.         cp2.append(list(row))
  148.     return cp2
  149.  
  150. #
  151. # The basic idea here is that if the patch is sitting right over
  152. #  the face, the three points p0, p1, p2 should get the patch .st
  153. #  coordinates (0,0), (1,0) and (0, 1) respectively.
  154. #
  155. def texcpFromFace(cp, face, editor):
  156.     "returns a copy of cp with the texture-scale of the face projected"
  157.     #    
  158.     # Note special code, which inhibits recentering threepoints
  159.     #
  160.     p0, p1, p2 = face.threepoints(6)
  161.     
  162.     def axis(p, p0=p0):
  163.         "turns a texp point into axis for computing b2 texcp's"
  164.         return (p-p0).normalized/abs(p-p0)
  165.  
  166.     def project(v, p0=p0, (s_axis, t_axis)=map(axis, (p1, p2))):
  167.         # note the wacko sign-flip for t
  168.         return quarkx.vect(v.xyz + ((v-p0)*s_axis, -(v-p0)*t_axis))
  169.  
  170.     return mapCp(project, cp)
  171.  
  172. def texFromFaceToB2(b2, face, editor):
  173.     "copies texture and scale from face to bezier"
  174.     b2["tex"] = face["tex"]
  175.     b2.cp = texcpFromFace(b2.cp, face, editor)
  176.  
  177. def b2FromCpFace(cp, name, face, editor):
  178.     b2 = quarkx.newobj(name+':b2')
  179.     b2.cp =  texcpFromFace(cp, face, editor)
  180.     b2["tex"]=face["tex"]
  181.     return b2
  182.  
  183. def cpFrom2Rows(row0, row2, bulge=None):
  184.     "makes cp from top & bottom rows & fills in middle"
  185.     if bulge is None:
  186.       bulge=(0.5, 1.0)
  187.     cp = [row0, None, row2]
  188.     cp[1] = map(lambda x, y, h=bulge[0]:h*x+(1-h)*y, cp[0], cp[2]) 
  189.     if bulge[1]!=1:
  190.         c=reduce(lambda x,y:x+y,cp[1])/float(len(cp[1]))
  191.         cp[1]=map(lambda v,c=c,b=bulge[1]:c+b*(v-c), cp[1])
  192.     return cp
  193.  
  194.  
  195. def b2From2Rows(row0, row2, texface, name, bulge=None, subdivide=1, subfunc=None):
  196.      cp = cpFrom2Rows(row0, row2, bulge)
  197.      if subdivide>1:
  198.          cp = subdivideRows(subdivide,cp, subfunc)
  199.      b2 = quarkx.newobj(name+":b2")
  200.      b2["tex"] = texface["tex"]
  201.      b2.cp = texcpFromFace(cp, texface, None)
  202.      return b2
  203.  
  204.  
  205. #
  206. # If u and v are images of the parameter axes, this matrix
  207. #  gives the associated linear mapping
  208. #
  209. def colmat_uv1(u,v):
  210.     "returns column matrix of u, v, and z axis vector tuples"
  211.     return quarkx.matrix((u[0], v[0], 0),
  212.                          (u[1], v[1], 0),
  213.                          (u[2], v[2], 1))
  214.  
  215. #
  216. # bcp is a flat array of control points, cp an array `rolled up'
  217. # along the columns.  The idea is to readjust the texture coordinates
  218. # of the bcp to compensate for distortion along the columns
  219. #
  220. def undistortColumns(cp):
  221.     ncp = copyCp(cp)   # this is what we return, after diddling it
  222.     h, w = len(cp), len(cp[0])
  223.     for j in range(w):  # for each column
  224. #        squawk(" col %d"%j)
  225.         #
  226.         # get info about distances between cp's
  227.         #
  228.         lengths = []
  229.         sum = 0
  230.         for i in range(1, h):
  231.             dist = abs(cp[i][j]-cp[i-1][j])
  232.             sum = sum + dist
  233.             lengths.append(sum)
  234.         if sum == 0:
  235.             sum = 1
  236.         #
  237.         # now rearrange texture cp's of bcp
  238.         #
  239.         start, end = cp[0][j], cp[h-1][j]
  240.         texstart, texend = map(lambda v:quarkx.vect(v.s, v.t, 0), (start,end))
  241.         texgap = texend-texstart
  242.         #
  243.         #  Now do it
  244.         #
  245. #        squawk('rockin')
  246.         for i in range(1,h-1):
  247.             s, t, x = (texstart + (lengths[i-1]/sum)*texgap).tuple
  248.             ncp[i][j]=quarkx.vect(cp[i][j].xyz+(s, t))
  249. #    squawk(`nbcp`)
  250.     return ncp      
  251.       
  252. def undistortRows(cp):
  253.     cp = transposeCp(cp)
  254.     cp = undistortColumns(cp)
  255.     return transposeCp(cp)
  256.  
  257. #
  258. # Getting approximate tangent planes at control points.
  259. #
  260.  
  261. #
  262. # The idea here is that at odd-numbered and quilt-end points, you
  263. #  take the actual derivatives, at intermedient end points you
  264. #  take the average of the derivative in and the derivative out.
  265. #  
  266. def dpdu(cp, i, j):
  267.   h = len(cp)
  268.   if i==0:
  269.     return 2*(cp[1][j]-cp[0][j])
  270.   elif i==h-1:
  271.     return 2*(cp[i][j]-cp[i-1][j])
  272.   else:
  273.     return (cp[i+1][j]-cp[i-1][j])
  274.     
  275. def dpdv(cp, i, j):
  276.   w = len(cp[0])
  277.   if j==0:
  278.     return 2*(cp[i][j+1]-cp[i][j])
  279.   elif j==w-1:
  280.     return 2*(cp[i][j]-cp[i][j-1])
  281.   else:
  282.     return cp[i][j+1]-cp[i][j-1]
  283.     
  284. def tanAxes(cp, i, j):
  285.   return dpdu(cp, i, j).normalized, dpdv(cp, i, j).normalized
  286.   
  287. #
  288. #  Derivative matrix for parameter->space mappings and
  289. #    parameter->plane mappings, at corners.
  290. #  Not defined at non-corners due to greater complexity and/or
  291. #    ill-definition (crinkles=no deriv at even-indexed cp's)
  292. #
  293. def d5(cp, (i, j)):
  294.     dSdu = dSdv = None
  295.     if i==0:
  296.         dSdu = cp[1][j]-cp[0][j]
  297.     elif i==len(cp)-1:
  298.         dSdu = cp[i][j]-cp[i-1][j]
  299.     if j==0:
  300.         dSdv = cp[i][1]-cp[i][0]
  301.     elif j==len(cp[0])-1:
  302.         dSdv = cp[i][j]-cp[i][j-1]
  303.     return dSdu, dSdv  
  304.     
  305.  
  306. #def faceTexFromCph(cph, face, editor):
  307. def texPlaneFromCph(cph, editor):
  308.     "projects texture-scale at cp handle to face, returning copy of face"
  309.     b2 = cph.b2
  310.     d5du, d5dv = d5(b2.cp, cph.ij)
  311.     if d5du is None or d5dv is None:
  312.         return None
  313.     #
  314.     # Derivatives of parameter->space and parameter->tex maps.
  315.     # S for space, T for texture (cap so diff from patch coords)
  316.     #
  317.     dSdp = colmat_uv1(d5du.xyz, d5dv.xyz)
  318.     dTdp = colmat_uv1((d5du.s, d5du.t, 1),
  319.                       (d5dv.s, d5dv.t, 1))
  320.     Mat = dSdp*~dTdp
  321.     #
  322.     # This mapping is the texture scale & offset (differential
  323.     #   of texture->space mapping)
  324.     #
  325.     def mapping(t3, offset=b2.cp[0][0], Mat=Mat):
  326.         texoffset = quarkx.vect(offset.s, offset.t, 0)
  327.         return Mat*(quarkx.vect(t3)-texoffset)+quarkx.vect(offset.xyz)
  328.     #
  329.     # Apply the texture differential to origin & two axes of texture
  330.     #   space.  Note wierdass sign-reversal (beaucoup de tah, Bill)
  331.     #
  332.     texp = map(mapping,((0,0,0),(1,0,0),(0,-1,0)))
  333.     #
  334.     # Now first project the texture onto a face tangent to the patch,
  335.     #   then project it onto the face we want.
  336.     #
  337.     new = quarkx.newobj("face:f")
  338. #    new = face.copy()
  339.     new.setthreepoints(texp,1)
  340.     new["tex"]=b2["tex"]
  341.     new.setthreepoints(texp,2,editor.TexSource)
  342.     return new
  343.  
  344. #
  345. #   The counterclockwise traversal of the edges
  346. #     supports using arithmetic to figure out how
  347. #     to `rotate' things for patch-merger & knitting
  348. #
  349. P_FRONT = 0   # first column of patch
  350. P_TOP = 1     # last row of patch 
  351. P_BACK = 2    # last column of patch
  352. P_BOTTOM = 3  # row 0 of patch
  353.  
  354.  
  355. def RotateCpCounter1(cp):
  356.     "returns a cp net where the old P_BACK is now P_TOP"
  357.     ncp = []
  358.     h = len(cp)
  359.     w = len(cp[0])
  360.     for j in range(w):
  361.         ncp.append(map(lambda i,cp=cp,k=w-j-1:cp[i][k],range(h)))
  362.     return ncp
  363.  
  364. def RotateCpCounter2(cp):
  365.     ncp = []
  366.     h = len(cp)
  367.     for i in range(h):
  368.       row = cp[h-i-1]
  369.       row = list(row)
  370.       row.reverse()
  371.       ncp.append(row)
  372.     return ncp
  373.  
  374. def RotateCpCounter(i, cp):
  375.     if i==0:
  376.         return copyCp(cp)
  377.     i=i%4
  378.     if i==0:
  379.         return copyCp(cp)
  380.     if i==1:
  381.         return RotateCpCounter1(cp)
  382.     if i==2:
  383.         return RotateCpCounter2(cp)
  384.     if i==3:
  385.         return RotateCpCounter1(RotateCpCounter2(cp))
  386.  
  387. def twistedRows(cp1, cp2):
  388.     lr, lc = len(cp1)-1, len(cp1[0])-1
  389.     e1, e2 = cp1[0][lc], cp1[lr][lc]
  390.     b1, b2 = cp2[0][0], cp2[lr][0]
  391.     if abs(e1-b1)>abs(e1-b2) and abs(e2-b2)>abs(e2-b1):
  392.        return 1
  393.     return 0
  394.       
  395.       
  396. def joinCp((tp1,X), cp1, (tp2,Y), cp2):
  397.     "returns cp1 extended to include cp2, assumes preconditions"
  398. #    squawk(`tp1-P_BACK`)
  399.     cp1 = RotateCpCounter(P_BACK-tp1, cp1)
  400.     cp2 = RotateCpCounter(P_FRONT-tp2, cp2)
  401. #    squawk(`cp1`)
  402. #    squawk(`cp2`)
  403.     twisted = twistedRows(cp1,cp2)
  404.     if twisted:
  405.        cp1.reverse()
  406.     ncp = map(lambda row1, row2:row1+row2[1:], cp1, cp2)
  407.     if twisted:
  408.        ncp.reverse()
  409.     return RotateCpCounter(tp1-P_BACK, ncp)
  410.  
  411. def knitCp((tp1,X), cp1, (tp2,Y), cp2):
  412.     "returns cp1 with edge knitted to cp2, assumes preconditions"
  413. #    squawk(`tp1-P_BACK`)
  414.     cp1 = RotateCpCounter(P_BACK-tp1, cp1)
  415.     cp2 = RotateCpCounter(P_FRONT-tp2, cp2)
  416. #    squawk(`cp1`)
  417. #    squawk(`cp2`)
  418.     last = len(cp1[0])-1
  419. #    ncp = copyCp(cp1)
  420.     twisted = twistedRows(cp1, cp2)
  421.     if twisted:
  422.       cp1.reverse()
  423.     for i in range(len(cp1)):
  424.         cp1[i][last]=cp2[i][0]
  425.     if twisted:
  426.       cp1.reverse()
  427.     squawk('done')
  428.     return RotateCpCounter(tp1-P_BACK, cp1)
  429.     
  430. def b2Point(u, p0, p1, p2):
  431.     return u*u*(p0-2*p1+p2)+u*(-2*p0+2*p1)+p0
  432. #    return (1-u)*(1-u)*p0 + 2*u*(1-u)*p1 + p2*u*u
  433.     
  434. #
  435. # This does 1 seg with 3 cp's, the crappy way.
  436. #
  437. def subdivideLine(n, p0, p1, p2):
  438.     "for n>=1, return 1+2n-tuple defining bezier quilt mesh line"
  439. #    squawk('subdiv '+`n`)
  440.     if n < 1: return
  441.     if n==1: return [p0, p1, p2]
  442.     retval = [p0]
  443.     last = p0
  444.     for i in range(n):
  445.         q = b2Point((i+.5)/n, p0, p1, p2)
  446.         p = b2Point((i+1.0)/n, p0, p1,p2)
  447.         m = b2midcp(last,q,p)
  448.         retval.append(m)
  449.         retval.append(p)
  450.         last = p
  451.     return retval
  452.  
  453. #
  454. # This is supposed to do a whole 1+2*n line
  455. #
  456. def subdivideRow(n, row, subfunc=None):
  457.     if subfunc==None:
  458.         subfunc=subdivideLine
  459.     length = len(row)
  460.     result = [row[0]]
  461.     for i in range(0,length-1,2):
  462. #       squawk(`i`)
  463. #       squawk(`result`)
  464.        line = subfunc(n, row[i], row[i+1], row[i+2])
  465. #       squawk(`line`)
  466.        result = result + subfunc(n, row[i], row[i+1], row[i+2])[1:]
  467. #    squawk(`result`)
  468.     return  result
  469.     
  470.  
  471. def subdivideRows(n, cp, func=None):
  472.     return map(lambda row,n=n,f=func:subdivideRow(n, row,f),cp)
  473.  
  474.  
  475. def subdivideColumns(n, cp, func=None):
  476.     return transposeCp(subdivideRows(n,transposeCp(cp),func))
  477.     
  478.  
  479. #
  480. # Attempt at a better circle approximation.
  481. #  the idea is to think of the b2 curve as an approximation
  482. #  to an image of a quarter-circle.
  483. # 
  484. # Derived from a suggestion by Alex Haarer.
  485. #
  486. def arcSubdivideLine(n, p0, p1, p2):
  487.     mat = matrix_u_v(p0-p1, p2-p1)
  488.     halfpi = math.pi/2.0
  489.     points = [quarkx.vect(1,0,0)]
  490.     last = points[0]
  491.     lastdir = quarkx.vect(-1,0,0)
  492.     for i in range(n):
  493.         a = halfpi*(i+1)/n
  494.         next = quarkx.vect(1.0-math.sin(a), 1.0-math.cos(a), 0)
  495.         nextdir = quarkx.vect(-math.cos(a), math.sin(a), 0)
  496.         mid = intersectionPoint2d(last,lastdir, next, nextdir)
  497.         points.append(mid)
  498.         points.append(next)
  499.         last = next
  500.         lastdir = nextdir
  501.     points = map (lambda v,mat=mat,d=p1:d+mat*v, points)
  502.     return points
  503.     
  504. #
  505. # get i, j from index position (row-after-row listing)
  506. #   think of a better name for this
  507. #
  508. def cpPos(p,b2):
  509.     i, j = divmod(p, b2.W)
  510.     return int(i), int(j)
  511.  
  512. def writecps(cp):
  513.     debug('cp: ')
  514.     for row in range(len(cp)):
  515.       for  col in range(len(cp[row])):
  516.         point = cp[row][col]
  517.         try:
  518. #          debug(" %d,%d: s: %6.2f t: %6.2f"%(row, col, cp[row][col][3], cp[row][col][4]))
  519.            debug(" %d,%d: s: %6.2f, t: %6.2f"%(row, col, point.s, point.t))
  520.         except:
  521.           debug(" notexcoords")
  522.  
  523.  
  524.  
  525. # ----------- REVISION HISTORY ------------
  526. #
  527. #
  528. #$Log: b2utils.py,v $
  529. #Revision 1.18  2002/12/29 04:18:33  tiglari
  530. #transfer fixes from 6.3
  531. #
  532. #Revision 1.17.10.1  2002/12/29 02:57:59  tiglari
  533. #texcpfromface now uses threepoints(6) to avoid recentering tex coords
  534. #
  535. #Revision 1.17  2001/03/20 11:01:51  tiglari
  536. #credit added
  537. #
  538. #Revision 1.16  2000/12/30 05:27:11  tiglari
  539. #cpPos function for mapping index position to i, j coordinates
  540. #
  541. #Revision 1.15  2000/09/04 21:24:23  tiglari
  542. #added procedures for better circular arc segments
  543. #
  544. #Revision 1.14  2000/09/02 11:22:35  tiglari
  545. #generalized subdivideRows/Columns to arbitrary quilts
  546. #
  547. #Revision 1.13  2000/08/23 12:12:34  tiglari
  548. #Added support for edge knitting; fixed join bug
  549. #
  550. #Revision 1.12  2000/07/24 12:47:40  tiglari
  551. #listCP function added
  552. #
  553. #Revision 1.11  2000/07/23 08:40:44  tiglari
  554. #faceTexFromCph removed; texPlaneFromCph added
  555. #
  556. #Revision 1.10  2000/06/26 22:51:55  tiglari
  557. #renaming: antidistort_rows/columns->undistortRows/Colunmns,
  558. #tanaxes->tanAxes, copy/map/transposecp->copy/map/transposeCP
  559. #
  560. #Revision 1.9  2000/06/25 23:48:01  tiglari
  561. #Function Renaming & Reorganization, hope no breakage
  562. #
  563. #Revision 1.8  2000/06/25 11:00:50  tiglari
  564. #fixed antidistortion crash when sum=0.  still wrong but doesn't crash
  565. #
  566. #Revision 1.7  2000/06/22 22:38:37  tiglari
  567. #added interpolateGrid (replacing an unused fn with a goofy name)
  568. #
  569. #Revision 1.6  2000/06/12 11:20:45  tiglari
  570. #Redid antidistort_columns, added antidistort_rows
  571. #
  572. #Revision 1.5  2000/06/04 03:21:25  tiglari
  573. #distortion reduction (elimination) for `rolled up' columns
  574. #
  575. #Revision 1.4  2000/06/03 18:01:28  alexander
  576. #added cvs header
  577. #
  578. #Revision 1.3  2000/06/03 12:59:33  tiglari
  579. #fixed arch duplicator maploading problem, hopefully
  580. #
  581. #Revision 1.2  2000/06/02 16:00:22  alexander
  582. #added cvs headers
  583. #
  584. #
  585. #